1017G - The Tree - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
int n,q,p[100003],col[100003];
vector<int>chn[100003];
int tp[100003],idx=1;
vector<int>e[100003];
int mxson[100003],sz[100003],wz[100003];
int k1,k2,k3,k4,k5,k6,k7,k8,k9;
void dfs(int now){
	sz[now]=1;
	for(auto i:e[now]){
		dfs(i);
		if(mxson[now]==0||sz[mxson[now]]<sz[i])mxson[now]=i;
		sz[now]+=sz[i];
	}
	return;
}
void divd_tree(int now,int mk){
	if(!now)return;
	chn[mk].push_back(now);
	divd_tree(mxson[now],mk);
	col[now]=mk;
	for(auto i:e[now]){
		if(i==mxson[now])continue;
		idx++;
		tp[idx]=i;
		divd_tree(i,idx);
	}
	return;
}
struct SegmentTree{
	int st;
	int ed;
	int val;
	int val2;
	int lzmk;
	int lzmk2;
}T[2000003];
void pushdown(int now){
	if(!T[now].lzmk2)return;
	T[now*2].val=T[now].lzmk*(T[now*2].ed-T[now*2].st+1);
	T[now*2].val2=max(T[now*2].val,T[now].lzmk);
	T[now*2].lzmk=T[now].lzmk;
	T[now*2].lzmk2=1;
	T[now*2+1].val=T[now].lzmk*(T[now*2+1].ed-T[now*2+1].st+1);
	T[now*2+1].val2=max(T[now*2+1].val,T[now].lzmk);
	T[now*2+1].lzmk=T[now].lzmk;
	T[now*2+1].lzmk2=1;
	T[now].lzmk2=0;
	T[now].lzmk=0;
	return;
}
void build(int now,int st,int ed){
	T[now].st=st;
	T[now].ed=ed;
	T[now].val=-(ed-st+1);
	T[now].val2=-1;
	if(st==ed)return;
	build(now*2,st,((st+ed)>>1));
	build(now*2+1,((st+ed)>>1)+1,ed);
	return;
}
void add(int now,int wz,int val){
	if(T[now].st>wz||T[now].ed<wz)return;
	if(T[now].st==T[now].ed){
		T[now].val+=val;
		T[now].val2+=val;
		return;
	}
	pushdown(now);
	add(now*2,wz,val);
	add(now*2+1,wz,val);
	T[now].val=T[now*2].val+T[now*2+1].val;
	T[now].val2=max(T[now*2+1].val2,T[now*2+1].val+T[now*2].val2);
	return;
}
void modify(int now,int l,int r,int val){
	if(T[now].st>r||T[now].ed<l)return;
	if(T[now].st>=l&&T[now].ed<=r){
		T[now].val=val*(T[now].ed-T[now].st+1);
		T[now].val2=max(T[now].val,val);
		T[now].lzmk2=1;
		T[now].lzmk=val;
		return;
	}
	pushdown(now);
	modify(now*2,l,r,val);
	modify(now*2+1,l,r,val);
	T[now].val=T[now*2].val+T[now*2+1].val;
	T[now].val2=max(T[now*2+1].val2,T[now*2+1].val+T[now*2].val2);
	return;
}
int Query(int now,int st,int ed){
	if(T[now].st>ed||T[now].ed<st)return 0;
	if(T[now].st>=st&&T[now].ed<=ed)return T[now].val;
	pushdown(now);
	return Query(now*2,st,ed)+Query(now*2+1,st,ed);
}
int stk[100003],tot;
void Query2(int now,int st,int ed){
	if(T[now].st>ed||T[now].ed<st)return;
	if(T[now].st>=st&&T[now].ed<=ed){
		stk[++tot]=now;
		return;
	}
	pushdown(now);
	Query2(now*2,st,ed);
	Query2(now*2+1,st,ed);
	return;
}
vector< pair<int,int> >stk2;
int calc(){
	int ret=-214748364;
	stk2.clear();
	stk2.shrink_to_fit();
	for(int i=1;i<=tot;i++)stk2.push_back(make_pair(T[stk[i]].st,stk[i]));
	sort(stk2.begin(),stk2.end());
	for(int i=tot-1,j=0;i>=0;i--){
		ret=max(ret,j+T[stk2[i].second].val2);
		j+=T[stk2[i].second].val;
	}
	return ret;
}
void getval(int now){
	if(now==0)return;
	Query2(1,wz[tp[col[now]]],wz[now]);
	getval(p[tp[col[now]]]);
	return;
}
int main(){
	//freopen("CF1017G.in","r",stdin);
	scanf("%d%d",&n,&q);
	for(int i=2;i<=n;i++){
		scanf("%d",&p[i]);
		e[p[i]].push_back(i);
	}
	dfs(1);
	tp[1]=1;
	divd_tree(1,1);
	for(int i=1,j=1;i<=idx;i++){
		for(auto u:chn[i])wz[u]=j++;
	}
	build(1,1,n);
	while(q--){
		scanf("%d%d",&k1,&k2);
		if(k1==1){
			add(1,wz[k2],1);
		}
		if(k1==2){
			modify(1,wz[k2],wz[k2]+sz[k2]-1,-1);
			tot=0;
			getval(k2);
			k3=calc();
			add(1,wz[k2],-k3-1);
		}
		if(k1==3){
			tot=0;
			getval(k2);
			k4=calc();
			if(k4>=0)puts("black");
			else puts("white");
		}
	}
	return 0;
}